/**
 * @name: 5-31日 学习时间复杂度
 * @return {*}
 */
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        // 目标是求 x的n次方

        // 1. 法一 直接是 n * n 时间复杂度是O(n)
        const function1 = (x, n) => {
            let result = 1
            for(let i = 0; i < n; i++) {
                result = result * x
            }
            return result;
        }
        // console.log(function1(3, 4));

        // 2. 法二 采用递归 
        // 每次递归n就做一次减1的操作 就是递归了n次，时间复杂度是O(n) 
        // 每次执行一个乘法操作，而乘法操作的时间复杂度是一个常数项O(1), => 最终的时间复杂度是O(n) = O(n * 1)
        // 时间复杂度排序: O(1)< O(logn)<O(n)<O(n^2)
        const function2 = (x, n) => {
            if(n === 0) {
                return 1 // 所有的数的0次方都等于1
            }
            return function2(x, n - 1) * x
        }
        // console.log(function2(3, 4));

        // 3. 法三 采用递归的其他方式
        const function3 = (x, n) => {
            if(n === 0) {
                return 1
            }
            let c = Math.floor(n / 2)
            if(n % 2 == 1) {
                console.log(`function3(${x}, ${c}) * function3*(${x}, ${c})*2`, function3(x, c) * function3(x, c) * 2);
                return function3(x, c) * function3(x, c) * 2
            }
            console.log(`function3(${x}, ${c}) * function3*(${x}, ${c})`, function3(x, c) * function3*(x, c));
            return function3(x, c) * function3*(x, c)
        }
        // console.log(function3(3, 4));
        // 4. 法四 采用递归的其他方式
        // n = 4, t = fn(3, 2) => 9 * 9
        // n = 2, t = fn(3, 1) => 3 * 3
        // n = 1, t = fn(3, 0) => 1 * 1 * 3
        // n = 0, return 1

        // 时间复杂度: 递归调用 => 每次递归调用都会除以2 所以这里一共调用了 logn次 每次调用都是一次乘法操作 是常数项的操作
        const function4 = (x, n) => {
            if(n === 0) {
                return 1
            }
            let t = function4(x, Math.floor(n / 2)) 
            if (n % 2 === 1) {
                return t * t * x
            }
            return t * t
        }
        console.log(function4(3, 4));
    </script>
</body>
</html>